package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-04 19:17
 * @description: Functions of this class is
 **/
public class 实现strStr {

    public static void main(String[] args) {
        System.out.println(strStr("mississippi","issip"));
    }
    public static int strStr(String haystack, String needle) {
        if(needle.equals("")){
            return 0;
        }
        if(haystack.length()<needle.length()){
            return -1;
        }
        int next[]=getNext(needle);
        int len1=haystack.length();
        int len2=needle.length();
        int i=0;
        int j=0;
        while (i<len1&&j<len2){
            if(j==-1||haystack.charAt(i)==needle.charAt(j)){
                i++;
                j++;
            }
            else{
                j=next[j];
            }
        }
        return j<len2?-1:i-len2;
    }
    private static int[] getNext(String needle){
        int len=needle.length();
        int next[]=new int[len];
        int j=0;
        int k=-1;
        next[0]=k;
        while (j<len-1){
            if(k==-1||needle.charAt(j)==needle.charAt(k)){
                next[++j]=++k;
                if(needle.charAt(j)==needle.charAt(k)){
                    next[j]=next[k];
                }
            }
            else{
                k=next[k];
            }
        }
        return next;
    }
}